package acwing._2LanQiao.test;
/**
 * @Project : AlgorithmLearning
 * @Package : ACWing._2LanQiao.test
 * @File : shortestPath.java
 * @Author : WangRuoyu
 * @Date : 2023/4/7 19:35
 */

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class shortestPath {
    static int n;
    static int m;
    static int[] h;
    static int[] e;
    static int[] w;
    static int[] next;
    static int idx = 0;

    static void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        next[idx] = h[a];
        h[a] = idx++;
    }

    static int[] dijkstra(int x) {
        PriorityQueue<int[]> pq = new PriorityQueue<>(((o1, o2) -> o1[1] != o2[1] ? o1[1] - o2[1] : o1[0] - o2[0]));
        int[] res = new int[n + 1];
        boolean[] st = new boolean[n + 1];
        Arrays.fill(res, 0x3f3f3f3f);
        res[x] = 0;
        pq.add(new int[]{x, 0});
        while (!pq.isEmpty()) {
            int[] point = pq.poll();
            int t = point[0];
            if (st[t]) continue;
            int dis = point[1];
            for (int i = h[t]; i != -1; i = next[i]) {
                int j = e[i];
                int c = w[i];
                if (res[j] > dis + c) {
                    res[j] = dis + c;
                    pq.add(new int[]{j, res[j]});
                }
            }
            st[t] = true;
        }
        return res;
    }

    static int[] spfa(int x) {
        int[] res = new int[n + 1];
        boolean[] st = new boolean[n + 1];
        Arrays.fill(res, 0x3f3f3f3f);
        res[x] = 0;
        Queue<Integer> q = new LinkedList<>();
        q.add(x);
        st[x] = true;
        while (!q.isEmpty()) {
            int t = q.poll();
            st[t] = false;
            for (int i = h[t]; i != -1; i = next[i]) {
                int j = e[i];
                int c = w[i];
                if (res[j] > res[t] + c) {
                    res[j] = res[t] + c;
                    if (!st[j]) {
                        q.add(j);
                        st[j] = true;
                    }
                }
            }
        }
        return res;
    }

//    static void floyd() {
//        for (int k = 1; k <= n; ++k) {
//            for (int i = 1; i <= n; ++i) {
//                for (int j = 1; j <= n; ++j) {
//                    dis[i][j] = Math.min(dis[i][j], dis[i][k] + dis[k][j]);
//                }
//            }
//        }
//    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] words = br.readLine().split(" ");
        n = Integer.parseInt(words[0]);
        m = Integer.parseInt(words[1]);
        h = new int[n + 1];
        Arrays.fill(h, -1);
        e = new int[2 * m + 10];
        w = new int[2 * m + 10];
        next = new int[2 * m + 10];
        for (int i = 0; i < m; ++i) {
            words = br.readLine().split(" ");
            int a = Integer.parseInt(words[0]);
            int b = Integer.parseInt(words[1]);
            int c = Integer.parseInt(words[2]);
            add(a, b, c);
            add(b, a, c);
        }
        int[] dis = dijkstra(1);
        System.out.println(dis[n]);
    }
}
